from typing import *
import time
import random

def get_nexts(s: str, n: int) -> List[int]:
    res = [0] * n
    res[0] = -1
    cn, i = 0, 2
    while i < n:
        if s[i-1] == s[cn]:
            res[i] = cn + 1
            i += 1
            cn +=1
        elif cn != 0:           # 加速匹配
            cn = res[cn]
        else:                   # 这一位就是0了
            i += 1
    return res

def idxOf(s1: str, s2: str) -> int:
    if (m := len(s1)) < (n:=len(s2)):
        return -1
    nexts = get_nexts(s2, n)
    i = j = 0
    while i < m and j < n:
        if s1[i] == s2[j]:      # 匹配的上
            i += 1
            j += 1
        elif nexts[j] != -1:    # 还能抢救
            j = nexts[j]
        else:                   # j = 0了, i这意味宣告失败, 到下一位开始匹配吧
            i += 1
    return i - n if j == n else -1



#############       for test
def generate_random_str(max_len: int) -> str:
    res = [None] * random.randint(1, max_len)
    for i in range(len(res)):
        res[i] = chr(random.randint(97, 122))
    return ''.join(res)


def function_test():
    ''' 功能测试 '''
    times = 10000
    max_len_1 = 500
    max_len_2 = 100
    print('测试开始')
    for _ in range(times):
        s1 = generate_random_str(max_len_1)
        s2 = generate_random_str(max_len_2)
        ans1 = idxOf(s1, s2)
        ans2 = s1.find(s2)
        if ans1 != ans2:
            print('OOPS!')
            print(s1, s2)
            print(ans1, ans2)
            break
    print("测试结束未打印 OOPS, 即表示测试通过")

if __name__ == '__main__':
    # function_test()
    s1 = 'aaaaaaaaaaacaaaaaaaaaaacaaaaabaaacaaaaaaaaaaaaaabaaaaaaaaaaaccaaaaabcaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabb'
    s2 = 'aaaaaaaaaaaaaaaaaaaaaaaab'
    t1 = time.time()
    print(time.time())
    ans1 = idxOf(s1, s2)
    t2 = time.time()
    print(time.time())
    ans2 = s1.find(s2)
    t3 = time.time()
    print(time.time())
    print('kmp: {}, 耗时{}s'.format(ans1, t2 - t1))
    print('系统提供: {}, 耗时{}s'.format(ans2, t3 - t2) )
